home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / ~Solutions Submitted / Problem 01 - Guinness / Solution.cp next >
Encoding:
Text File  |  1998-06-19  |  4.1 KB  |  151 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 01 - Mode Sort
  3.  
  4. This problem is to sort an input string of N characters, N<1000000, based on
  5. the number of times a character occurs in the input.  The most frequently
  6. occurring character should be sorted to the front of the string, followed by
  7. the next most frequently occurring character, etc.  For characters occurring
  8. the same number of times, the character that occurs first in the input should
  9. be sorted to the front.
  10.  
  11. Header specification
  12.  
  13. pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile );
  14.  
  15. Input specification
  16.  
  17. The infile input file contains the characters.  Input characters other than
  18. those printable low ascii characters c, 0x20<c<0x7f, must be ignored.
  19.  
  20. Output specification
  21.  
  22. The outfile must be created and then filled with the sorted characters.  It's
  23. final length should be exactly the same as the count of characters in the
  24. allowed range (0x20<c<0x7f) (which may be shorter than the infile file length).
  25.  
  26. Sample input
  27.  
  28. abcdefghabbcccdddeee
  29. or
  30. 012345678911234567892123456789312345678941234567895123456789612345678971234567891
  31.  
  32. Sample output
  33.  
  34. ccccddddeeeebbbaafgh
  35. or
  36. 111111111122222222233333333344444444455555555566666666677777777788888888999999990
  37. */
  38.  
  39. #include "Solution.h"
  40.  
  41. // Fill in your solution and then submit this folder
  42. // Team Name: Team Guinness
  43.  
  44. static unsigned char seenfirst(unsigned char orderseen[0x100], int x, int y)
  45.     {
  46.     int i;
  47.     for (i=0; i<0x100; i++)
  48.         {
  49.         if (orderseen[i] == x) return(x);
  50.         if (orderseen[i] == y) return(y);
  51.         }
  52.     return(0);
  53.     }
  54.  
  55. static unsigned char findmostcommon(unsigned long h[0x100], unsigned char orderseen[0x100])
  56.     {
  57.     int best = 0, i;
  58.     for (i=1; i<0x100; i++)
  59.         {
  60.         if      (h[best] < h[i]) best = i;
  61.         else if (h[best] == h[i] && seenfirst(orderseen, i, best) == i) best = i;
  62.         }
  63.     return(best);
  64.     }
  65.  
  66. pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile )
  67.     {
  68.     int i, j, uniquenumseen = 0;
  69.     Ptr InPtr = NULL;
  70.     Ptr InEnd = NULL;
  71.     OSErr err = noErr;
  72.     short ReadRefNum = 0, WriteRefNum = 0;
  73.     long BytesRemaining = 0;
  74.     unsigned long histogram[0x100];
  75.     unsigned char charseen[0x100], orderseen[0x100];
  76.  
  77.     for (i=0; i<0x100; i++) histogram[i] = charseen[i] = orderseen[i] = 0;
  78.  
  79.     // Allocate some storage
  80.     unsigned long BufferSize = MaxBlock();
  81.     Handle Buffer = NewHandle(BufferSize);
  82.     while (!Buffer && BufferSize > 1024)
  83.         { BufferSize >>= 1; Buffer = NewHandle(BufferSize); }
  84.     if (!Buffer) return(MemError());
  85.     HLock(Buffer);
  86.  
  87.     err = FSpOpenDF(infile, fsRdPerm, &ReadRefNum);
  88.     if (err) goto exit;
  89.     
  90.     err = GetEOF(ReadRefNum, &BytesRemaining);
  91.     if (err) goto exit;
  92.     
  93.     while (BytesRemaining)
  94.         {
  95.         // Grab some bytes from the file
  96.         long inOutCount = BytesRemaining;
  97.         if (inOutCount > BufferSize) inOutCount = BufferSize;
  98.         err = FSRead(ReadRefNum, &inOutCount, *Buffer);
  99.         if (err) goto exit;
  100.         if (inOutCount == 0) { DebugStr("\pError: FSRead read nothing"); goto exit; }
  101.         InPtr = *Buffer;
  102.         InEnd = InPtr + inOutCount;
  103.         BytesRemaining -= inOutCount;
  104.         
  105.         // Munch on the bytes
  106.         while (InPtr < InEnd)
  107.             {
  108.             unsigned char c = *InPtr++;
  109.             if (c > 0x20 && c < 0x7F)
  110.                 {
  111.                 if (!charseen[c]) { charseen[c] = 1; orderseen[uniquenumseen++] = c; }
  112.                 histogram[c]++;
  113.                 }
  114.             }
  115.         }
  116.     
  117.     FSClose(ReadRefNum); ReadRefNum = 0;
  118.     
  119.     // Make sure output file exists (will give error if it already exists)
  120.     FSpCreate(outfile, 'CWIE', 'TEXT', 0);
  121.     
  122.     err = FSpOpenDF(outfile, fsWrPerm, &WriteRefNum);
  123.     if (err) goto exit;
  124.     
  125.     err = SetEOF(WriteRefNum, 0);
  126.     if (err) goto exit;
  127.     
  128.     for (i=0; i<0x100; i++)
  129.         {
  130.         unsigned char c = findmostcommon(histogram, orderseen);
  131.         long inOutCount = histogram[c];
  132.         if (inOutCount > BufferSize) inOutCount = BufferSize;
  133.         for (j=0; j<inOutCount; j++) Buffer[0][j] = c;
  134.         while (histogram[c])
  135.             {
  136.             long inOutCount = histogram[c];
  137.             if (inOutCount > BufferSize) inOutCount = BufferSize;
  138.             err = FSWrite(WriteRefNum, &inOutCount, *Buffer);
  139.             if (err) goto exit;
  140.             if (inOutCount == 0) { DebugStr("\pError: FSWrite wrote nothing"); goto exit; }
  141.             histogram[c] -= inOutCount;
  142.             }
  143.         }
  144.  
  145.     exit:
  146.     if (WriteRefNum) FSClose(WriteRefNum);
  147.     if (ReadRefNum) FSClose(ReadRefNum);
  148.     if (Buffer) DisposeHandle(Buffer);
  149.     return(err);
  150.     }
  151.